package leetcode_day._2021._202103;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @data 2021/3/31 21:37
 * 思路：
 *   求数组的子集，属于组合
 *   就是在数组中取出 0 ,..., 数组长度个数进行组合
 *   使用回溯来取得所有的组合
 *   由于题目给出的数组可能会重复，所以要先排序，这样相同的两个数会相邻
 *   所以当当前数和前一个数相同时，直接跳过
 *   但这里有一个问题，就是这样直接跳过了，就少了几种组合
 *   比如 nums=[1, 2, 2]，如果跳过的话，结果就没有 [2, 2], [1, 2, 2] 了
 *   所以，要考虑啥时能够真正跳过，在定义一个布尔类型的 used 数组，第二个 2 只有当第一个 2 用过了才能使用，
 *   这样表示在第二个 2 使用的时候，第一个 2 已经遍历过了所有的可能，而这时第一个 2 对应的 used 为 false 这也是一种剪枝
 *   这里还可以剪枝，当数组中剩余的数无法组合成目标长度，则直接结束
 */
public class _31_90 {

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        for (int i = 0; i <= nums.length; i++) {
            dfs(0, i, nums, list, ans, used);
        }
        return ans;
    }
    public void dfs(int begin, int len, int[] nums, List<Integer> list, List<List<Integer>> ans, boolean[] used) {
        if (list.size() == len) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = begin; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            if (nums.length - i < (len - list.size())) break;
            list.add(nums[i]);
            used[i] = true;
            dfs(i + 1, len, nums, list, ans, used);
            used[i] = false;
            list.remove(list.size() - 1);
        }
    }
}
